In general, incoming packets from several different networks are forwarded to their destination by routers using information such as the prefix of the destination address located in a packet header of an incoming packet and a router table. The router table for each router contains records of the best routes to various network destinations in the form addresses for the devices connected to the router. The address of the next device, which is connected to the router, that the router is to direct an incoming packet toward in order for the packet to reach the packet's final destination is called a next hop. The next hop for an incoming packet is computed by determining the longest prefix in the router table that matches the destination address of the packet; the packet is then routed to the destination specified by the next hop associated with the longest prefix.
Router tables generally operate in one of two modes: static (offline) or dynamic (online). In the static mode, update requests are performed offline using a background processor. With some periodicity, a new and updated forwarding table is then created. In the dynamic mode, lookup and update requests are processed in the order they appear. Thus, a lookup cannot be done until a preceding update has been done.
Many of the data structures developed for the representation of a router table are based on the fundamental binary trie structure. For a binary trie structure, branching is done based on the bits in the search key. The node in which a prefix is to be stored is determined by doing a search using that prefix as key. A node N is defined to be a node in a binary trie. Q(N) is defined as the bit string defined by the path from the root to N. Specifically, Q(N) is the prefix that corresponds to N. The next hop corresponding to Q(N) is stored in N.data in case Q(N) is one of the prefixes in the router table. For any destination address d, the longest matching prefix can be found by following a path beginning at the trie root and dictated by d. The last prefix encountered on this path is the longest prefix that matches d.
Several strategies have been proposed to improve the lookup performance of binary tries. For example, LC tries (S. Nilsson and G. Karlsson, Fast address look-up for Internet routers, IEEE Broadband Communications, 1998), Lulea (M. Degermark, A. Brodnik, S. Carlsson, and S. Pink., Small forwarding tables for fast routing lookups, Proceedings of SIGCOMM, 3-14, 1997), tree bitmap (W. Eatherton, G. Varghese, Z. Dittia, Tree bitmap: hardware/software IP lookups with incremental updates, Computer Communication Review, 34(2): 97-122, 2004), multibit tries (V. Srinivasan and G. Varghese, Faster IP lookups using controlled prefix expansion, ACM Transactions on Computer Systems, Feb. 1-40, 1999, shape shifting tries (H. Song, J. Turner, and J. Lockwood, Shape shifting tries for faster IP route lookup, Proceedings of 13th IEEE International Conference on Network Protocols, 2005), and hybrid shape shifting tries (W. Lu and S. Sahni, Succinct representation of static packet classifiers, University of Florida, 2006) have been employed. Other earlier partitioning schemes are limited to one front-end array and one-level prefix partitioning. The strides of current partitioning tables are usually fixed and not data dependent. In addition, earlier partitioning schemes represent all partitions using the same base structure. Although existing schemes are designed to keep the number of memory accesses required for an update at an acceptable level, they may increase the worst-case number of memory accesses required for a lookup and also increase the total memory required to store the structure. (See M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, Survey and taxonomy of IP address lookup algorithms, IEEE Network, 2001, 8-23 and S. Sahni, K. Kim, and H. Lu, Data structures for one-dimensional packet classification using most-specific-rule matching, International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN), 2002, 3-14)
Accordingly, there exists a need for a method that provides less memory accesses for lookup, and less memory required overall.